class Solution {
public:
    Node *insert(Node *head, int insertVal) {
        Node *p = head, *maxNode = head;
        while (p) {
            if (p->val > p->next->val) maxNode = p;
            if (p->val <= insertVal && p->next->val >= insertVal) {
                break;
            }
            if (p->next == head) {
                p = maxNode;
                break;
            }
            p = p->next;
        }

        if (p) {
            p->next = new Node(insertVal, p->next);
        } else {
            head = new Node(insertVal);
            head->next = head;
        }

        return head;
    }
};